import { random } from "game-random";
// 普里姆算法生成连通图的二维数组
// 初始化数组
function initArray(r: number, c: number): number[][] {
    return [...Array(2 * r + 1)].map((_, index) => {
        if ((index + 1) % 2) {
            return Array(2 * c + 1).fill(1);
        } else {
            return [...Array(2 * c + 1).keys()].map((i) => (i + 1) % 2);
        }
    });
}

/** 处理数组，产生最终的数组 */
function process(arr: number[][], r: number, c: number, seed?: string) {
    //acc存放已访问队列，noAccess存放没有访问队列
    const count = r * c;
    const Access = [];
    const noAccess = Array(count).fill(0);

    //定义空单元上下左右偏移
    let offs = [-c, c, -1, 1],
        offR = [-1, 1, 0, 0],
        offC = [0, 0, -1, 1];
    //随机从noAccess取出一个位置
    let pos = random(count, seed);
    noAccess[pos] = 1;
    Access.push(pos);
    let loopTime = 0;
    while (Access.length < count) {
        let ls = -1,
            offPos = -1;
        //找出pos位置在二维数组中的坐标
        let pr = (pos / c) | 0,
            pc = pos % c,
            co = 0,
            o = 0;
        //随机取上下左右四个单元
        while (++co < 5) {
            const innerSeed = seed ? co + loopTime + seed : seed;
            o = random(5, innerSeed);
            ls = offs[o] + pos;
            let tpr = pr + offR[o];
            let tpc = pc + offC[o];
            if (
                tpr >= 0 &&
                tpc >= 0 &&
                tpr <= r - 1 &&
                tpc <= c - 1 &&
                noAccess[ls] == 0
            ) {
                offPos = o;
                break;
            }
        }
        if (offPos < 0) {
            let innerSeed = seed ? seed + loopTime++ : seed;
            pos = Access[random(Access.length, innerSeed)];
        } else {
            pr = 2 * pr + 1;
            pc = 2 * pc + 1;
            //相邻空单元中间的位置置0
            arr[pr + offR[offPos]][pc + offC[offPos]] = 0;
            pos = ls;
            noAccess[pos] = 1;
            Access.push(pos);
        }
    }
    return arr;
}

/**
 * 最小生成树生成方形迷宫的算法
 */
export function createMaze(
    row: number,
    col: number,
    seed?: string
): number[][] {
    const temp = initArray(row, col);
    return process(temp, row, col, seed);
}
